/**
 * @file   zrena.h
 * @author karpar Hu <huzhili@gmail.com>
 * @date   Tue May  5 01:46:12 2009
 * 
 * @brief  Automacally memory pool class
 * 
 * 
 */

#ifndef _ZRENA_H_
#define _ZRENA_H_

#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <vector>

class BaseZrena {
protected:
/** 
 * We can't make a zrena directly; only a subclass of one
 * 
 * @param first_block 
 * @param block_size 
 */
  BaseZrena(char* first_block, const size_t block_size);
public:
  virtual ~BaseZrena();

  virtual void Reset();

/**
 * A handle to pointer in an zrena. An opaque type, with default
 * copy and assignment semantics.
 */
  class Handle {
  public:
    static const uint32_t kInvalidValue = 0xFFFFFFFF; /**< int32 */
    Handle() : handle_(kInvalidValue) { }
/// Default copy constructors are fine here.
    bool operator==(const Handle& h) const { return handle_ == h.handle_; }
    bool operator!=(const Handle& h) const { return handle_ != h.handle_; }

    uint32_t hash() const { return handle_; }
    bool valid() const { return handle_ != kInvalidValue; }
  private:
/// Zrena needs to be able to access the internal data.
    friend class BaseZrena;

    explicit Handle(uint32_t handle) : handle_(handle) { }

    uint32_t handle_;
  };
  
  virtual char* vAlloc(size_t size) = 0;
  virtual void vFree(void *memory, size_t size) = 0;
  virtual char* vRealloc(char *memory, size_t old_size, size_t new_size) = 0;
  virtual char* vAllocWithHandle(const size_t size, Handle* handle) = 0;
  
/** 
 * Set the alignment to be used when Handles are requested. This can
 * only be setted for an zrena that is empty-it cannot be changed on 
 * the fly.The alignment must be a power of 2 that the block size is
 * divisable by.the default alignment is 1
 * @param align alignment size
 */
  void set_handle_alignment(int align) {
    assert(align > 0 && 0 == (align & (align - 1)));
    assert(static_cast<size_t>(align) < block_size_);
    assert((block_size_ % align) == 0);
    assert(is_empty());
    handle_alignment_ = align;
  }

/** 
 * Retrieve the memory pointer that the supplied handle refers to.
 * Calling this with an invalid handle will assert-fail.
 * @param h the handler
 * 
 * @return the pointer
 */
  void *HandleToPointer(const Handle& h) const;

  class Status {
  private:
    friend class BaseZrena;
    size_t bytes_allocated_;
  public:
    Status() : bytes_allocated_(0) { }
    size_t bytes_allocated() const {
      return bytes_allocated_;
    }
  };

/** 
 * Accessors and stats counters.
 * This accessors isn't so useful here, but is included so we can be
 * type-compatible. This is, we defina zrena() because ZrenaAllocator
 * does, and that way you can template on either of these and kown it
 * is safe to call zrena().
 * @return 
 */
  virtual BaseZrena* zrena() { return this; }
  size_t block_size() const { return block_size_; }
  int block_count() const;
  bool is_empty() const {
    /// must check count in case we allocated a block larger than block size
    return freestart_ == freestart_when_empty_ && 1 == block_count();
  }

#ifdef __i386__
  static const int kDefaultAlignment = 4;
#else
  static const int kDefaultAlignment = 8;
#endif

protected:
  void MakeNewBlock();
  void* GetMemoryFallback(const size_t size, const int align);
  void* GetMemory(const size_t size, const int align) {
    assert(remaining_ <= block_size_); // an invariant
    if ( size > 0 && size < remaining_ && align == 1) { // common case
      last_alloc_ = freestart_;
      freestart_ += size;
      remaining_ -= size;
      return reinterpret_cast<void*>(last_alloc_);
    }
    return GetMemoryFallback(size, align);
  }

  // This doesn't actually free any memory except for the last piece
  // allocated. Or we can choose to call it,Undo!
  void ReturnMemory(void *memory, const size_t size) {
    if (memory == last_alloc_ && size == freestart_ - last_alloc_) {
      remaining_ += size;
      freestart_  = last_alloc_;
    }
  }

/** 
 * This is used by Realloc()--usually we Realloc just by copying the
 * bigger space, but for the last alloc we can realloc by growing the
 * the region.
 * @return 
 */
  bool AdjustLastAlloc(void* last_alloc, const size_t newsize);

  // Since using different alignment for different handles would make
  // the handle incompletible(e.g., we could endup  with same handle
  // value referenceing two different allocations, the alignment is not
  // as an argument to GetMemoryWithHandle, and handle_alignment is
  // automatically for all GetMemoryWithHandle calls.
  void* GetMemoryWithHandle(const size_t size, Handle *handle);

  Status status_;
private:
  struct AllocatedBlock {
    char *mem;
    size_t size;
  };

/** 
 * The returned AllocatedBlock* is valid until the next call to Alloc
 * or Reset.(i.e. anything that might affect overflow_blocks.
 * 
 * @return 
 */
  AllocatedBlock *AllocNewBlock(const size_t block_size);
  const AllocatedBlock *IndexToBlock(int index) const;

  const int first_block_own;    /**< 1 if they pass 1st block, 0 else */
  const size_t block_size_;    
  char *freestart_; /**< beginning of the free space in most recent block */
  char *freestart_when_empty_;  /**< beginning of the space when empty */
  char *last_alloc_;            /**< used to make sure ReturnBytes() is safe */
  size_t remaining_;

  // vector not effecient enough,using an array.
  int blocks_alloced_;         /**< how many of the first_blocks_ have been alloced */
  AllocatedBlock first_blocks_[16]; /**< the length of this array is anbitrary */
  // if the first_blocks aren't enough, expend into overflow_blocks_.
  std::vector<AllocatedBlock>* overflow_blocks_;
  int handle_alignment_;         /**< Alignment to be used when Handles are requested. */

  void FreeBlocks();            /**< Free all except first block. */
  BaseZrena(const BaseZrena&); // disallow copying
  void operator=(const BaseZrena&);
};


class UnsafeZrena : public BaseZrena {
public:
  explicit UnsafeZrena(const size_t block_size)
    : BaseZrena(NULL, block_size) { }

  UnsafeZrena(char *first_block, const size_t block_size)
    : BaseZrena(first_block, block_size) { }

  char* Alloc(const size_t size) {
    return reinterpret_cast<char*>(GetMemory(size, 1));
  }
  void* AllocAligned(const size_t size, const int align) {
    return GetMemory(size, align);
  }
  char* Calloc(const size_t size) {
    void* return_value = Alloc(size);
    memset(return_value, 0, size);
    return reinterpret_cast<char*>(return_value);
  }
  void* CallocAligned(const size_t size, const int align) {
    void* return_value =  AllocAligned(size, align);
    memset(return_value, 0 ,size);
    return return_value;
  }
  // Free does nothing except for the last piece allocated.
  void Free(void *memory, size_t size) {
    ReturnMemory(memory, size);
  }

  typedef BaseZrena::Handle Handle;
  char *AllocWithHandle(const size_t size, Handle* handle) {
    return reinterpret_cast<char*>(GetMemoryWithHandle(size, handle));
  }

  virtual char* vAlloc(size_t size) {
    return Alloc(size);
  }
  virtual void vFree(void *memory, size_t size) {
    Free(memory, size);
  }
  virtual char* vRealloc(char *memory, size_t old_size, size_t new_size) {
    return Realloc(memory, old_size, new_size);
  }
  virtual char* vAllocWithHandle(const size_t size, Handle* handle) {
    return AllocWithHandle(size, handle);
  }

  char* Memdup(const char* s, size_t bytes) {
    char *newstr = Alloc(bytes);
    memcpy(newstr, s, bytes);
    return newstr;
  }
  char* MemdupPlusNUL(const char *s, size_t bytes) {
    char *newstr = Alloc(bytes+1);
    memcpy(newstr, s, bytes);
    newstr[bytes] = '\0';
    return newstr;
  }
  Handle MemdupWithHandle(const char *s, size_t bytes) {
    Handle handle;
    char* newstr = AllocWithHandle(bytes, &handle);
    memcpy(newstr, s, bytes);
    return handle;
  }
  char* Strdup(const char* s) {
    return Memdup(s, strlen(s)+1);
  }
  char* Strdup(const char *s, size_t n) {
    const char* eos = reinterpret_cast<const char*>(memchr(s, '\0', n));
    const size_t bytes = (eos == NULL) ? n + 1 : eos - s + 1;
    char *ret = Memdup(s, bytes);
    ret[bytes-1] = '\0';
    return ret;
  }

  char* Realloc(char *s, size_t oldsize, size_t newsize);
  char* Shrink(char *s, size_t newsize) {
    AdjustLastAlloc(s, newsize);
    return s;
  }
  Status status() const { return status_; };
private:
  UnsafeZrena(const UnsafeZrena&); // disallow copying
  void operator=(const UnsafeZrena&);
};

#endif /* _ZRENA_H_ */
